package impl.sort;

import anaydis.sort.SorterType;
import com.sun.org.apache.xml.internal.utils.IntStack;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 05/10/2011
 * Time: 13:21:45
 * To change this template use File | Settings | File Templates.
 */
public class QuickNRSorter extends AbstractSorter {
    public QuickNRSorter() {
        super(SorterType.QUICK_NON_RECURSIVE);
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        sort(c, list, 0, list.size()-1);
    }
    private <T> void sort(Comparator<T> c, List<T> list, int l, int r) {
        IntStack s = new IntStack();
        s.push(l);
        s.push(r);
        while(!s.empty()){
            r = s.pop();
            l = s.pop();
            if(r-l>0){
                int i = partition(c, list, l, r);
                if(i>l){
                    s.push(l);
                    s.push(i-1);
                }
                if(i<list.size()-2){
                    s.push(i+1);
                    s.push(r);
                }
            }
        }

    }
    private <T> int partition(Comparator<T> c, List<T> list, int l, int r) {
        int pivot = r;
        int i = l;
        int j = pivot-1;
        while(i!=j){
            while(!greater(c, list, i, pivot)&&(i<j)){
                i++;
            }
            while(greater(c, list, j, pivot)&&(i<j)){
                j--;
            }
            if(i!=j){
                swap(list, i, j);
            }
        }
        if(greater(c, list, i, pivot)){
            swap(list, pivot, i);
        }
        if(i==pivot-1){
            return pivot;
        }
        return i;
    }
}
